#include <iostream>
using namespace std;
#include <vector>



void merge(vector<int>& arr,int left , int mid , int right)
{
  int temp[right-left+1] ;


  int i = left;
  int j = mid + 1;
  int k = 0;

  while (i <= mid  && j <= right)
  {
    if (arr[i] <= arr[j])
    {
      temp[k++] = arr[i++];
    }
    else 
    {
      temp[k++] = arr[j++];
    }
  }

  while (i <= mid)
  {
    temp[k++] = arr[i++];
  }

  while (j <= right)
  {
    temp[k++] = arr[j++];
  }

  for (int i = left; i <= right; i++)
  {
    arr[i] = temp[i - left];
  }
}


void mergesort(vector<int>& arr , int left , int right)
{
  if (left >= right)
  {
    return; 
  }

  int mid = left + (right-left)/2;
  mergesort(arr , left ,  mid);
  mergesort(arr , mid + 1 , right);

  merge(arr , left , mid , right);
}





int main()
{
  vector<int> ans = {1 , 11, 15, 2, 4, 6, 8, 34 , 12 , 44};
  int right = ans.size();
  int left = 0;
  mergesort(ans , left , right);
  for (auto x : ans)
  {
    cout << x << endl;
  }
}
